package a_doubleWrite;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * @author: luolidong
 * @create: 2021-07-19 11:17
 * @version: 1.0
 */
public class L22 {
    public List<String> generateParenthesis(int n) {
        //左右括号相同为n
        //先添加(,后)
        List<String> list=new ArrayList<>();
        dfs(list, n,n,"");
        return list;
    }
    public void dfs(List<String> list,int leftNum,int rightNum,String s){
        if(leftNum==0&&rightNum==0){
            list.add(s);
            return;
        }
        //)数量不能超过(
        if(leftNum>rightNum) return;
        if(leftNum>0){
            dfs(list, leftNum-1, rightNum, s+'(');
        }
        if(rightNum>0){
            dfs(list, leftNum, rightNum-1, s+')');
        }
    }
}
